//
// Created by zx208 on 2024/10/17.
//

// 给定键值按升序排列的带头结点的单链表La和Lb，
// 将其合并成升序排列的单链表Lc，并返回新链表的表头指针
// 要求利用原表的结点数据空间

// 思路：原题目要求辅助空间为就地空间 所以我们直接在两原链表上进行操作 后果就是会破坏原链表的结构

#include "../SingleLinkedList.h"

LinkedList Create_List_R(LinkedList head, int n){

    // 先创建头指针
    head = (LinkedList) malloc(sizeof( LNode));
    head->next = NULL;

    // 创建一个工作指针
    LinkedList node = head;

    for (int i = 0; i < n; ++i) {
        LinkedList p = (LinkedList) malloc(sizeof( LNode));
        int data;
        scanf(" %d", &data);
        p->data = data;
        p->next = node->next; // 即 p->next = NULL;
        node->next = p;
        node = p;
    }
    return head;
}

void PrintLL(LinkedList L){
    LNode *node = L->next;
    while(node){
        printf("%d ", node->data);
        node = node->next;
    }
}


LinkedList Merge(LinkedList La, LinkedList Lb){
    LinkedList a = La->next, b = Lb->next, Lc = La , c = Lc;

    while(a && b){
        if(a->data < b->data) {
            c->next = a;
            c = a;
            a = a->next;
        } else{
            c->next = b;
            c = b;
            b = b->next;
        }
    }

    if(a) c->next = a;
    else c->next = b;

    free(Lb);

    return Lc;
}

int main(void){
    LinkedList La = NULL, Lb = NULL, Lc = NULL;
    La = Create_List_R(La, 3);
    Lb = Create_List_R(Lb, 3);

    Lc = Merge(La, Lb);
    PrintLL(Lc);
    return 0;
}

// 1 2 6
// 3 4 5

// 1 3 5
// 2 4 6